BZOJ 3519 消棋子

Description

消棋子是一个有趣的游戏。游戏在一个r * c的棋盘上进行。棋盘的每个格子,要么是空,要么是一种颜色的棋子。同一种颜色的棋子恰好有两个。每一轮,玩家可以选择一个空格子(x, y),并选择上下左右四个方向中的两个方向,如果在这两个方向上均存在有棋子的格子,而且沿着这两个方向上第一个遇到的棋子颜色相同,那么,我们将这两个棋子拿走,并称之为合法的操作。否则称这个操作不合法,游戏不会处理这个操作。游戏的目的是消除尽量多的棋子。
给出这样一个游戏和一个人的玩法。你需要:
z 指出此人能消去多少棋子。
z 给出一种能消去最多棋子的方案。

Input

第一行给出了整数r, c。第二行给出了整数n,表示不同颜色数。接下来n行,第i行含4个整数a[i], b[i], c[i], d[i],表示颜色为i的两个格子分别是(a[i], b[i]), (c[i], d[i])。然后是一个整数m,表示此人的操作数。接下来m行,每行有2个整数和2个字母,代表了他选择的格子,以及两个方向。我们用“UDLR”分别表示上下左右。

Output

第一行输出此人能消去多少棋子。第二行含一个整数k(0 ≤k ≤10^6),表示你给出的方案的操作数。接下来k行,每行2个整数和2个字母,代表你选择的格子以及两个方向。

Sample Input

4 4
4
1 1 1 4
1 2 3 4
1 3 3 2
4 1 2 3
6
2 3 U R
2 1 D R
2 2 L R
2 4 L D
3 1 L R
3 3 L U

Sample Output

2
4
4 3 L U
3 3 L U
3 2 R U
1 2 L R

Solution

用treap来判两个点中间是不是为空
第一问直接判
第二问外面套链表扫,感觉是O(n^2*log(n))的但是过了
(傻逼的不swap左右只有30分QAQ)

Code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
#include<bits/stdc++.h>

#define maxn 100000+5
#define maxt 800000+5
#define set(a,b) memset(a,(b),sizeof(a))

using namespace std;

typedef long long ll;

struct treap{
int s[2],v;
int num,w,k;
}tr[maxt];

struct node{
int x,y;
friend bool operator < (node const &a,node const &b)
{return a.x==b.x?a.y<b.y:a.x<b.x;}
}ch[maxn][2];

struct solution{
int x,y;
char op[2];
}sol[maxn];

map<node,int> hash;
int Next[maxn],Last[maxn];
int root[2][maxn],size;
int n,m,r,c,ans,res;

void update(int x)
{

int l=tr[x].s[0],r=tr[x].s[1];
tr[x].num=tr[l].num+tr[r].num+1;
}

void rotate(int &x,int t)
{

int s=tr[x].s[t];
tr[x].s[t]=tr[s].s[t^1],tr[s].s[t^1]=x;
update(x),update(s),x=s;
}

void delet(int &x,int w)
{

if( tr[x].w==w ){
int l=tr[x].s[0],r=tr[x].s[1];
if( l+r ){
int t=(tr[l].v<tr[r].v);
rotate(x,t),delet(tr[x].s[t^1],w);
update(x);
}
else x=0;
return ;
}
int t=(w>tr[x].w);
delet(tr[x].s[t],w),update(x);
}

void insert(int &x,int w,int k)
{

if( x==0 ){
x=++size,tr[x].num=1;
tr[x].v=rand(),tr[x].w=w,tr[x].k=k;
return ;
}
int t=(w>tr[x].w);
insert(tr[x].s[t],w,k);
if( tr[size].v>tr[x].v ) rotate(x,t);
else update(x);
}

void inst(node a,int k)
{

int x=a.x,y=a.y;
insert(root[0][x],y,k);
insert(root[1][y],x,k);
}

void delt(node a)
{

int x=a.x,y=a.y;
delet(root[0][x],y);
delet(root[1][y],x);
}

int query(int x,int w)
{

if( x==0 ) return 0;
int l=tr[x].s[0],r=tr[x].s[1];
if( tr[x].w==w ) return tr[l].num+1;
if( w<=tr[x].w ) return query(l,w);
else return tr[l].num+1+query(r,w);
}

int find(int x,int k)
{

if( x==0 ) return 0;
int l=tr[x].s[0],r=tr[x].s[1];
if( tr[l].num+1==k ) return tr[x].k;
if( k<=tr[l].num ) return find(l,k);
else return find(r,k-tr[l].num-1);
}

int getres(char *s,int x,int y)
{

int cnt;
if( s[0]=='L' ){
cnt=query(root[0][x],y);
return find(root[0][x],cnt);
}
if( s[0]=='R' ){
cnt=query(root[0][x],y);
return find(root[0][x],cnt+1);
}
if( s[0]=='U' ){
cnt=query(root[1][y],x);
return find(root[1][y],cnt);
}
if( s[0]=='D' ){
cnt=query(root[1][y],x);
return find(root[1][y],cnt+1);
}
}

void init()
{

set(root,0),hash.clear();
for(int i=1;i<=n;i++){
hash[ch[i][0]]=1,hash[ch[i][1]]=1;
inst(ch[i][0],i),inst(ch[i][1],i);
}
}

bool check(int kd,int p,int l,int r)
{

if( l>r ) swap(l,r);
int cnt=query(root[kd][p],r-1)-query(root[kd][p],l);
return cnt==0;
}

void solve()
{

printf("%d\n",ans),init();
for(int i=1;i<=n;i++)
Last[i]=i-1,Next[i]=i+1;
Next[0]=1,Next[n]=-1;
bool flag=true;
while( flag ){
flag=false;
for(int i=Next[0];i!=-1;i=Next[i]){
if( ch[i][0].x==ch[i][1].x ){
int x=ch[i][0].x,l=ch[i][0].y,r=ch[i][1].y;
if( l>r ) swap(l,r);
if( l!=r-1 && check(0,x,l,r) ){
res++,flag=true;
sol[res].x=x,sol[res].y=l+1;
sol[res].op[0]='L',sol[res].op[1]='R';
hash[ch[i][0]]=0,hash[ch[i][1]]=0,delt(ch[i][0]),delt(ch[i][1]);
Next[Last[i]]=Next[i],Last[Next[i]]=Last[i];
}
}
else if( ch[i][0].y==ch[i][1].y ){
int l=ch[i][0].x,r=ch[i][1].x,y=ch[i][0].y;
if( l>r ) swap(l,r);
if( l!=r-1 && check(1,y,l,r) ){
res++,flag=true;
sol[res].x=l+1,sol[res].y=y;
sol[res].op[0]='U',sol[res].op[1]='D';
hash[ch[i][0]]=0,hash[ch[i][1]]=0,delt(ch[i][0]),delt(ch[i][1]);
Next[Last[i]]=Next[i],Last[Next[i]]=Last[i];
}
}
else{
int x=ch[i][0].x,y=ch[i][1].y;
if( !hash[(node){x,y}] && check(0,x,y,ch[i][0].y) && check(1,y,x,ch[i][1].x) ){
res++,flag=true;
sol[res].x=x,sol[res].y=y;
if( x<ch[i][1].x ) sol[res].op[0]='D';
else sol[res].op[0]='U';
if( y<ch[i][0].y ) sol[res].op[1]='R';
else sol[res].op[1]='L';
hash[ch[i][0]]=0,hash[ch[i][1]]=0,delt(ch[i][0]),delt(ch[i][1]);
Next[Last[i]]=Next[i],Last[Next[i]]=Last[i];
}
else{
x=ch[i][1].x,y=ch[i][0].y;
if( !hash[(node){x,y}] && check(0,x,y,ch[i][1].y) && check(1,y,x,ch[i][0].x) ){
res++,flag=true;
sol[res].x=x,sol[res].y=y;
if( x<ch[i][0].x ) sol[res].op[0]='D';
else sol[res].op[0]='U';
if( y<ch[i][1].y ) sol[res].op[1]='R';
else sol[res].op[1]='L';
hash[ch[i][0]]=0,hash[ch[i][1]]=0,delt(ch[i][0]),delt(ch[i][1]);
Next[Last[i]]=Next[i],Last[Next[i]]=Last[i];
}
}
}
}
}
printf("%d\n",res);
for(int i=1;i<=res;i++)
printf("%d %d %c %c\n",sol[i].x,sol[i].y,sol[i].op[0],sol[i].op[1]);
}

int main()
{

#ifndef ONLINE_JUDGE
freopen("3519.in","r",stdin);
freopen("3519.out","w",stdout);
#endif
scanf("%d%d%d",&r,&c,&n);
for(int i=1;i<=n;i++){
scanf("%d%d%d%d",&ch[i][0].x,&ch[i][0].y,&ch[i][1].x,&ch[i][1].y);
if( ch[i][0].x>ch[i][1].x ) swap(ch[i][0],ch[i][1]);
}
scanf("%d",&m),init();
for(int i=1;i<=m;i++){
char op[2][5];
int x,y,res[2];
scanf("%d%d%s%s",&x,&y,op[0],op[1]);
if( hash[(node){x,y}]!=0 ) continue;
res[0]=getres(op[0],x,y);
res[1]=getres(op[1],x,y);
if( res[0]==res[1] && res[0]!=0 ){
ans++,delt(ch[res[0]][0]),delt(ch[res[0]][1]);
hash[ch[res[0]][0]]=0;
hash[ch[res[0]][1]]=0;
}
}
solve();
return 0;
}